This invention relates to an automatic wiring design device or an automatic router for use in designing wiring paths on a wiring board, such as a print circuit board, an integrated circuit board, or the like.
Heretofore, an automatic router of the type described designs interconnections or wirings between points of connections by the use of either a shove aside technique or a rip-up technique, as described by William A. Dees, Jr. and Patrick G. Karger on pages 432 to 439 in proceedings of 19th Design Automation Conference (1982) and entitled "Automated rip-up and rerouter techniques". More particularly, the shove aside technique is for shoving an existing wiring into adjacent routing resources to secure a room for a new connection while the rip-up technique is for removing a previously defined wiring to reroute a new connection instead of the previously defined wiring.
Herein, use of the shoving aside technique should successively shove each existing wiring aside in a trial-and-error manner until such shoving aside operation becomes successful when the shoving aside operation is unsuccessful in connection with a certain existing wiring. Therefore, the shoving aside technique is very time-consuming.
On the other hand, the rip-up technique should repeatedly remove the previously defined wiring to reroute the new connection in a trial-and-error manner. Therefore, the rip-up technique is also time-consuming so as to improve a degree of connectivity.
In addition, a description about automatic routing is found in VLSI design (April 1984), on pages 35-43. Such an automatic routing is executed on the basis of a channel-routing algorithm, a a line-search algorithm, and a maze router.